Segmenting digital images into regions of distinct types is a useful form of image processing that can be very useful to more clearly depict features in the image. It has significant uses in both military and civilian applications to permit both more rapid and more accurate analysis of many types of imagery.
For example, segmentation can automate the mapping and labeling of images from synthetic aperture radar and satellite according to landscape type (for example, agricultural, forest, lake) and so enhance surveillance. See, e.g., X. Descombes, M. Moctezuma, H. Maitre, J. P. Rudant, “Coastline detection by a Markovian segmentation on SAR images,” Signal Process. 55, 123-132 (1996). Similarly, segmentation of underwater sonar images can be used to delineate sea floor regions of mud, sand, and rock, which can aid in mine detection by predicting the degree of mine burial in the seafloor and in allowing optimal sonar settings to detect such buried mines. See, e.g., F. W. Bentrem, W. E. Avera, J. Sample, “Estimating Surface Sediments Using Multibeam Sonar,” Sea Technol. 47, 37 (2006).
In addition to aiding in the analysis of remote imaging, image segmentation can be used with medical imaging to aid health workers in identifying abnormalities such as tumors in medical images. See, e.g., D. L. Pham, C. Xu, J. L. Prince, “Current Methods in Medical Image Segmentation,” Annu. Rev. Biomed. Eng. 2, 315 (2000); Y. H. Yang, M. J. Buckley, S. Dudoit, T. P. Speed, “Comparison of Methods for Image Analysis on DNA Microarray Data,” J. Comput. Graph. Stat. 11, 108 (2002); S. Peng, B. Urbanc, L. Cruz, B. T. Hyman, H. E. Stanley, “Neuron recognition by parallel Potts segmentation,” P. Natl. Acad. Sci. USA 100, 3847 (2003); V. Grau, A. U. J. Mewes, M. Alcañiz, “Improved Watershed Transform for Medical Image Segmentation Using Prior Information,” IEEE T. Med. Imaging 23, 447 (2004).
In general, image segmentation is performed by classifying image regions by color, intensity, and texture, with only the latter two being considered in grayscale segmentation. There can be a large number of possible intensities and texture types in a digital image, and thus sufficiently representing the intensities and textures in the image can be an important part of image processing.
A grayscale digital image may be represented as a matrix of numerical values which indicate the intensity or brightness (gray level) of the corresponding image pixel. Techniques for image segmentation (such as thresholding and histogram methods) that focus solely on intensity are the most computationally efficient since they generally require just one or two passes through the intensity matrix. While classification by intensity is a straightforward assessment of the brightness/darkness of an image pixel or group of pixels (as with histogram segmentation methods such as those described in Pham et al., supra), texture classification is much more complex. See Pham et al., supra; see also T. Asano, D. Z. Chen, N. Katoh, T. Tokuyama, “Polynomial-Time Solutions to Image Segmentation,” Int. J. Comput. Geom. Ap. 11, 145 (2001). Texture can be described by the spatial relationship of the intensities (i.e. “graininess”) of an image region. However, accurately identifying regions of different texture can be relatively expensive in terms of computation time because of the complexity and diversity involved. See T. Asano, supra. Many prior art image segmentation techniques process in exponential time, i.e., the time required to process a digital image increases exponentially with the number of pixels contained in the image. See K. Tanaka, “Statistical-mechanical approach to image processing,” J. Phys. A-Math. Gen. 35, R81-R150 (2002). Although advances have been made via certain approximations such as the Bethe approximation, image segmentation using these methods still requires power-law time, i.e., 10 times the number of pixels takes about 1000 times (10 to the 3rd power) as long. See K. Tanaka, supra; see also K. Tanaka, H. Shouno, M. Okadak, D. M. Titterington, “Accuracy of the Bethe approximation for hyperparameter estimation in probabilistic image processing,” J. Phys. A-Math. Gen. 37, 8675 (2004). However, real-time processing (such as for sonar imagery) requires much greater efficiency and thus these methods have not proven satisfactory.